def fact(n):
	if n == 1:
		return 1
	return n * fact(n-1)

print(fact(5))
print(fact(10))

def fact(n):
	return fact_iter(n, 1)

def fact_iter(num,product):
	if num == 1:
		return product
	return fact_iter(num - 1, num * product)
'''这是廖雪峰发的：
def fact(n):
    return fact_iter(n, 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)'''

print(fact(10))

#廖雪峰说这样就不会有栈溢出了，但是为什么还是有上限？为什么还是会报错？
#报错如下————————————————————————————————————————————————————————————————：
'''Traceback (most recent call last):
    print(fact(1000))
    return fact_iter(n, 1)
    return fact_iter(num - 1, num * product)
    return fact_iter(num - 1, num * product)
    return fact_iter(num - 1, num * product)
  [Previous line repeated 993 more times]
    if num == 1:
RecursionError: maximum recursion depth exceeded in comparison'''
#这个好蠢啊，因为fact_iter也被调用了（n+1)次，这个尾递归优化有什么卵用吗？


def move(n, a, buffer, c):
    if(n == 1):
        print(a,"->",c)
        return
    move(n-1, a, c, buffer)
    move(1, a, buffer, c)
    move(n-1, buffer, a, c)
move(3, "a", "b", "c")

print (move(3,1,2,3))


#-----------------------
/**
我把3个盘子的汉诺塔全部通过代码演示，按缩进原则，每一个缩进即进一个递归函数，每打印一次即中止当前递归,也就是每个print
说明:
    1.n = 3, n = 2, n = 1是每次执行if(n == 1)的结果，这里就不写判断了，相信童鞋们也能看懂，也就是n不等与1时就减1进入递归
    2.请注意a,b,c柱每次进入函数的顺序，不要被形参带错路了，看准每次函数参数的实参 
**/
move(3, "a", "b", "c")
n=3:
    //开始从a上移动n-1即2个盘子通过c移动到b,以腾出c供a最后一个盘子移动
    move(2, "a","c","b")
    n=2:
    //开始进行n=2的一个递归，把当前a('a')柱上的n-1个盘子通过c('b'）移动到b('c')
        move(1, "a", "b", "c")
        n=1:
        //n=2的第一个递归完成,打印结果，执行当前子函数剩余代码
            print("a", "->", "c") 
        move(1, "a", "c", "b")
        n=1:
            print("a", "->", "b")
        move(1, "c", "a", "b")
        n=1:
            print("c", "->", "b")
    　   //到这里完成了a柱上面的n-1即是2个盘子的移动
//开始把a柱上最后一个盘子移动到c柱上
move(1, "a", "b", "c")
n=1:
    print("a", "->", "c")
    //到这里完成移动a柱上的最后一个盘子到c柱上 
move(2, "b", "a", "c")
n=2:
//开始进行n=2的第二个递归,即把当前b('b')的盘子(n-1个)通过a('a')移动到c('c')上
    move(1, "b", "c", "a")
    n=1:
    //n=2 的第二个递归完成，打印结果并执行当前子函数的剩余代码
        print("b", "->", "a")
    move(1, "b", "a", "c")
    n=1:
        print("b", "->", "c")
    move(1, "a", "b", "c")
    n=1:
        print("a", "->", "c")
        //到这里把b上的盘子通过a移动到c,
//整个代码执行完毕,汉诺塔移动完成
